/*
Source : https://leetcode.com/problems/word-ladder/
Author : nflush@outlook.com
Date   : 2016-05-20
*/

/*
127. Word Ladder
Total Accepted: 75511 Total Submissions: 383637 Difficulty: Medium

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

    Only one letter can be changed at a time
    Each intermediate word must exist in the word list

For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

    Return 0 if there is no such transformation sequence.
    All words have the same length.
    All words contain only lowercase alphabetic characters.

Subscribe to see which companies asked this question
*/
class Solution {
    
public:
    int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList) {
        int dis = calcDis(beginWord, endWord);
        if (dis < 2) return dis +1;

        vector<bool> isPur(wordList.size());
        queue<int> q;
        for (int i = 0; i < wordList.size(); i++){
            isPur[i] = (calcDis(endWord, wordList[i]) == 1);
            if (1 == calcDis(beginWord, wordList[i])){
                q.push[i];
            }
        }
        vector<bool> isDel(wordList.size(), false);
        vector<int> disv(wordList.size(), 1);
        while(!q.empty()){
            int str = q.front();
            q.pop();
            string word = wordList[str];
            for (int i = 0; i < wordList.size(); i++){
                if (isDel[i]){
                    continue;
                }
                if(1 == calcDis(word, wordList[i])){
                    if(isPur[i]){
                        return disv[str] + 2;
                    }
                    isDel[i] = true;
                    disv[i] = disv[str]+ 1;
                    q.push(i);
                }
            }
        }
        return 0;
    }
private:
    int calcDis(const string &s1, const string &s2){
        int ret = 0;
        for(int i = 0; i <s1.size();i++){
            if(s1[i] != s2[i]) ret++;
        }
        return ret;
    }
};

